
public class Test11 {
    static int C = 30;//背包容量
    static int N = 3;
    static int weights[] = {16, 15, 15};//重量
    static int values[] = {45, 25, 25};//价值
    static boolean[] x = {false, false, false};//作为判断选不选的问题
    //保存最大价值
    static int maxValuse = 0;

    //回溯核心
    //w：当前背包所放物品重量和
    //v：当前背包所放物品价值和
    public static void backtrack(int level, int w, int v) {
        if (level == N) {
            output(v);
        } else {
            x[level] = false;//不选
            backtrack(level + 1, w, v);
            x[level] = true;//选
            if (legal(w + weights[level]))
                backtrack(level + 1, w + weights[level], v + values[level]);
        }
    }

    //判断当前背包重量是不是合法
    public static boolean legal(int w) {
        return w <= C;
    }

    //v：当前的价值
    public static void output(int v) {
        maxValuse = Math.max(v, maxValuse);
    }

    public static void main(String[] args) {
        backtrack(0, 0, 0);
        System.out.println("满足背包重量条件的最大价值：" + maxValuse);
    }
}